﻿using System;
using System.Collections.Generic;
using System.ComponentModel.Design.Serialization;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace CloudCUtils
{
    /// <summary>
    /// 数组工具类
    /// </summary>
    public static class ArrayUtils
    {
        public static string PrintToString<T>(T[]objs)
        {
            string res = "";
            foreach (T obj in objs)
            {
                res += obj.ToString();
            }
            return res;
        }

        /// <summary>
        /// 有序数组二分查找
        /// </summary>
        /// <param name="values">有序数组</param>
        /// <param name="target">目标值</param>
        /// <param name="start">起始索引</param>
        /// <param name="end">结束索引</param>
        /// <returns>目标值所在索引</returns>
        public static int BinarySearch(int[] values, int target, int start, int end)
        {
            int res = -1;
            int left = start;
            int right = end;
            int mid ;
            while (left<=right) {
                mid = (left + right) / 2;
                if (values[mid].Equals(target))
                {
                    res = mid;
                    break;
                }
                else
                {
                    if (values[mid]<target)
                    {
                        left = mid + 1;
                    }
                    else if (values[mid] > target)
                    {
                         right = mid - 1;
                    }
                }              
            }
            return res;
        }

        

        /// <summary>
        /// 冒泡排序
        /// </summary>
        /// <param name="nums"></param>
        //
        //相邻两两比较，交换位置，记录交换次数。不停循环这一过程，直到某次循环交换次数为0
        //注意：每一次循环之后，未排序部分的最大值就会被“冒泡”到最后的位置，进入有序的部分。
        //所以，对于长度为n的数组，最多循环n-1轮即可排序完成
        //那么下一次循环时，只循环无序的部分就可以了
        //时间复杂度O(n^2)，空间复杂度O(1)
        //稳定性：稳定。因为排序过程中，两个有相等值的元素的相对位置不变
        public static void BubbleSort(int[]nums)
        {
            if (nums == null || nums.Length == 0) return;

            int swapcount = 0;
            for(int i=0;i<nums.Length-1; i++)
            {
                for(int j = 0; j < nums.Length - 1 - i; j++)
                {
                    if (nums[j] > nums[j + 1])
                    {
                        int tmp = nums[j];
                        nums[j] = nums[j + 1];
                        nums[j + 1] = tmp;
                        swapcount++;
                    }
                }
                if (swapcount == 0) break;
                else swapcount = 0;
            }
            
            
        }

        /// <summary>
        /// 插入排序
        /// </summary>
        /// <param name="nums"></param>
        /// 
        //插入排序两种写法。
        //插入排序的本质是，从未排序部分顺序取值，从已排序部分逆序取值，当待排值大于已排序值时，待排序值不动
        //当待排序值小于已排序时，二者交换位置
        //稳定的排序.相同值的元素在排序前后相对位置不变，
        //因为只有未排序元素值大于已排序元素值的情况下才会交换位置，若相等是不交换位置的，所以相对位置不变
        //时间复杂度O（n^2）
        //空间复杂度O(1)
        public static void InsertionSort(int[]nums)
        {
            if(nums == null || nums.Length <= 1) return;
            //for (int i = 1; i < nums.Length; i++)
            //{
            //    int cur = nums[i];
            //    for(int j = i - 1; j >= 0; j--)
            //    {
            //        if (cur < nums[j])
            //        {
            //            nums[j + 1] = nums[j];
            //            nums[j] = cur;
            //        }
            //        else
            //        {
            //            break;
            //        }
            //    }
            //}

            for(int i = 1; i < nums.Length ; i++)
            {
                for(int j = i - 1; j >= 0; j--)
                {
                    if (nums[j] > nums[j + 1])
                    {
                        int tmp = nums[j];
                        nums[j] = nums[j + 1];
                        nums[j + 1] = tmp;
                    }
                    else break;
                }
            }
        }

        /// <summary>
        /// 选择排序
        /// </summary>
        /// <param name="nums"></param>
        /// 
        //每次选择未排序值的最大值或最小值，放在已排序序列的最后，也就是未排序序列的首位
        //不稳定的排序，如对 5 7 5 3 9 排序，第一次交换后为3 7 5 5 9，前5 在 后5的后边了，相对位置改变
        //时间复杂度O(n^2)
        //空间复杂度O（1）
        public static void SelectionSort(int[]nums)
        {
            if(nums==null|| nums.Length <= 1) return;
            
            
            for(int i=0;i< nums.Length ; i++)//遍历全部未排序元素，对全部元素进行排序
            {
                int minindex=i;//设定最小值的下标为未排序序列的第一个
                for(int j= i; j < nums.Length ; j++)//寻找未排序序列的最小值下标
                {
                    if (nums[j] < nums[minindex])
                    {
                        minindex = j;
                    }
                }
                if (minindex != i)
                {
                    int tmp = nums[i];
                    nums[i] = nums[minindex];
                    nums[minindex] = tmp;
                }
                else continue;//未排序序列最小值就是未排序序列的第一个元素，则不需要交换位置
                
            }
        }

        /// <summary>
        /// 计数排序
        /// </summary>
        /// <param name="nums"></param>
        /// 
        //用一个计数数组记录待排序列中各值出现的次数，之后在按照计数数组的顺序以此重新赋值给原数组
        //注意，创建的计数数组的长度和待排序列元素跨度相关，即最大值和最小值只差
        //待排序列跨度过大会导致计数数组过大
        //时间复杂度O(n+k),n是遍历待排序列把其中元素放到计数数组，k是遍历计数数组把元素在放回原数组
        //空间复杂度O(k)
        //不能直接排序负数。
        //计数排序是用来排序0到100之间的数字的最好的算法
        public static void CountingSort(int[]nums)
        {
            int max = nums[0];
            int min = nums[0];
            for(int i = 0; i < nums.Length; i++)
            {
                if (nums[i] > max){
                    max= nums[i];
                }
                if (nums[i] < min)
                {
                    min = nums[i];
                }
            }
            int[] tmp = new int[max - min + 1];//计数数组
            for(int i= 0; i< nums.Length ;i++)
            {
                tmp[nums[i]-min]++;
            }
            int index = 0;
            for(int i=0;i<tmp.Length; i++)
            {
                int count= tmp[i];
                while(count > 0)
                {
                    nums[index] = i+min;
                    index++;
                    count--;
                }
            }
        }

        /// <summary>
        /// 希尔排序
        /// </summary>
        /// <param name="nums"></param>
        /// 
        //递减增量排序，是对插入排序的改进，是一种分组插入排序，基于步进值分组，逐组插入排序
        //按照一个步进值分组进行插入排序，没排序一次后步进值递减，最后步进值为1，对整个序列进行排序
        //时间复杂度平均O(n^1.3)到O(n^1.5),具体的复杂度和选择的增量序列也就是步进值的选择有关
        //空间复杂度O(1)
        //不稳定排序。对于插入排序来说，是相邻元素比较，是稳定的。
        //而希尔排序步进值不为1时，比较的不是相邻的元素，所以对于相同值的元素，再排序前后相对位置可能改变
        public static void ShellSort(int[] nums)
        {
            if(nums==null || nums.Length==1) return;

            for (int step=nums.Length/2;step>=1;step/=2)
            {
                for(int i=step;i<nums.Length;i+=step)
                {
                    int cur = nums[i];
                    for (int j = i - step; j >= 0; j = j - step)
                    {
                        if (cur < nums[j])
                        {
                            nums[j+step] = nums[j];
                            nums[j] = cur;
                        }
                        else
                        {
                            break;
                        }
                    }
                }
            }
        }

        /// <summary>
        /// 归并排序
        /// </summary>
        /// <param name="nums"></param>
        /// 
        //递归思想实现，先对左右两部分排序后再合并，而对于左右任一部分，也拆成左右两部分进行排序再合并
        //时间复杂度O(nlog2n)
        //空间复杂度O（n）
        //稳定排序
        public static int[] MergeSort( int[] nums)
        {
            return SubMergeSort(nums);
        }

        private static int[] SubMergeSort(int[] nums)
        {
            if (nums.Length <= 1) return nums;

            int[] arr1 = new int[nums.Length / 2];
            int[] arr2 = new int[nums.Length - nums.Length / 2];
            for (int i = 0; i < arr1.Length; i++)
            {
                arr1[i] = nums[i];
            }
            for (int i = 0; i < arr2.Length; i++)
            {
                arr2[i] = nums[i + arr1.Length];
            }
            arr1=SubMergeSort(arr1);
            arr2=SubMergeSort(arr2);
            int[] res = Merge(arr1, arr2);
            return res;
        }
        /// <summary>
        /// 合并有序数组
        /// </summary>
        /// <param name="arr1"></param>
        /// <param name="arr2"></param>
        /// <returns></returns>
        private static int[] Merge(int[] arr1, int[] arr2)
        {
            int i1 = 0;
            int i2=0;
            int[] res = new int[arr1.Length+arr2.Length];
            int index = 0;
            while(i1 < arr1.Length&&i2<arr2.Length)
            {
                if (arr1[i1] < arr2[i2])
                {
                    res[index] = arr1[i1];
                    i1++;
                }
                else
                {
                    res[index] = arr2[i2];
                    i2++;
                }
                index++;
            }
            if (i1 == arr1.Length )
            {
                for(int i=i2; i<arr2.Length; i++) {
                    res[index]=arr2[i];
                    index++;
                }
            }
            if (i2 == arr2.Length )
            {
                for(int i=i1; i<arr1.Length; i++)
                {
                    res[index] = arr1[i];
                    index++;
                }
            }
            return res;
        }
        /// <summary>
        /// 快速排序
        /// </summary>
        /// <param name="nums"></param>
        /// 
        //选择一个基准值，使待排序列中小于它的再它左边，大于它的在它右边
        //再递归地对左右两侧序列排序
        //时间复杂度O（nlog2n）
        //空间复杂度O（1）
        //不稳定排序，元素交换位置时相同值元素相对位置可能改变
        public static void QuickSort(int[]nums)
        {
            SubQuickSort(nums, 0, nums.Length - 1);
        }

        private static void SubQuickSort(int[] nums, int start,int end)
        {
            if (nums == null || end-start < 1) return;
            int tag = nums[start];
            int left = start, right =end;
            while (left < right)
            {
                while (left < right && nums[right] >= tag)
                {
                    right--;
                }
                nums[left] = nums[right];
                while (left < right && nums[left] <= tag)
                {
                    left++;
                }
                nums[right] = nums[left];
            }
            nums[left] = tag;
            SubQuickSort(nums, start, left - 1);
            SubQuickSort(nums,left+1, end);
        }
    }
}
